In computer graphics, a computer is used to generate digital data that represents the projection of surfaces of objects in, for example, a three-dimensional scene, illuminated by one or more light sources, onto a top-dimensional image plane, to simulate the recording of the image by, for example, a camera. The simulated camera may include a lens for projecting the image of the scene onto the image plane, or it may comprise a pinhole camera in which case no lens is used. The two-dimensional image is in the form of an array of picture elements (which are variably referred to as “pixels” or “pels”), and the digital data generated for each pixel represents the color and luminance of the scene as projected onto the image plane at the point of the respective pixel in the image plane. The surfaces of the objects may have any of a number of characteristics, including shape, color, specularity, texture and so forth, which are preferably rendered in the image as closely as possible, to provide a realistic-looking image. Generally, the contributions of the light reflected from the various points in the scene to the pixel value representing the color, and intensity of a particular pixel are expressed in the form of the one or more integrals of relatively complicated functions. Since the integrals used in computer graphics generally do not have a closed-form solution, numerical methods must be used to evaluate them to generate the pixel value. Typically, a methodology referred to as the “Monte Carlo” method has been used in computer graphics to numerically evaluate the integrals. Generally, in the Monte Carlo method, to evaluate an integral
                              〈          f          〉                =                              ∫                                          [                                  0                  ,                  1                                )                            s                                                                      ⁢                                    f              ⁡                              (                x                )                                      ⁢                                                  ⁢                          ⅆ              x                                                          (        1        )            where f(x) is a real function defined on an integration domain comprising the “s”-dimensional unit cube [0,1)s (that is, an s-dimensional cube each dimension of which includes “zero,” and excludes “one”), a random point set Pr=(ξ1, . . . ξr)⊂[0,1)s of “r” independently realized points ξi, i=1, . . . , r, is generated over the integration domain. The random points ξi are used as sample points for which sample values f(ξi) are generated for the function f(x). An estimate ƒ for the value of the integral (equation (1)) is generated as
                                          〈            f            〉                    ≈                      f            _                          =                              1            r                    ⁢                                    ∑                              i                =                1                            r                        ⁢                                                  ⁢                          f              ⁡                              (                                  ξ                  i                                )                                                                        (        2        )            As the number “r” of sample points that are used in generating the sample values f(ξi) increases, the value of the estimate ƒ will converge toward the actual value of the integral <ƒ>. Generally, the distribution of values of the estimate ƒ that will be generated for various values of “r,” that is, for various numbers of sample points ξi are distributed around the actual value <ƒ> with a standard deviation σ which can be estimated by
                    σ        =                                            1                              N                -                1                                      ⁢                          (                                                                    f                    2                                    _                                -                                                      f                    _                                    2                                            )                                                          (        3        )            if the sample points ξi used to generate the sample values f(ξi) are statistically independent, that is, if the points ξi are truly positioned at random in the integration domain. This yields the probabilistic error bound
                              Prob          ⁡                      (                                                                                                                      ∫                                                                        [                                                      0                            ⁢                                                          ,                              0                                                        ⁢                            1                                                    )                                                s                                                                                                                                  ⁢                                                                  f                        ⁢                                                                                                  (                        x                        )                                            ⁢                                              ⅆ                        x                                                                              -                                                            1                      r                                        ⁢                                                                  ∑                                                  k                          =                          1                                                r                                            ⁢                                                                                          ⁢                                              f                        ⁡                                                  (                                                      ξ                            k                                                    )                                                                                                                                                ≤                                                3                  ⁢                                      σ                    ⁡                                          (                      f                      )                                                                                        r                                                      )                          ≈                  0.997          .                                    (        4        )            The rate of convergence of
  O  ⁡      (          1              r              )  is independent of the smoothness of the integrand f(x) and the number “s” of dimensions comprising the integration domain.
Several strategies can be used to improve convergence of the estimate ƒ to the actual value <ƒ> of the integral. One strategy, which is described in the aforementioned Grabenstein patent application, is to use a low-discrepancy, strictly deterministic point methodology to generate the set of sample points that will be used in generating the sample values f(ξi) for the estimate. A low-discrepancy, strictly deterministic methodology will ensure that the sample points are distributed throughout the integration domain [0,1)s without clumping in particular regions, which can occur if the sample points are randomly distributed.
Another strategy to improve the convergence is to stratify the integration domain [0,1)s into a number “K” of disjoint strata Aj, such that
                    [                  0          ,          1                )            s        =                  ⋃                  j          =          1                K            ⁢              A        j              ,and separately evaluate the resulting integrals
                                          ∫                                          [                                  0                  ,                  1                                )                            s                                                                      ⁢                                    f              ⁡                              (                x                )                                      ⁢                                                  ⁢                          ⅆ              x                                      =                              ∑                          j              =              1                        K                    ⁢                                          ⁢                                    ∫                              A                j                                                                                  ⁢                                          f                ⁡                                  (                  x                  )                                            ⁢                                                          ⁢                              ⅆ                x                                                                        (        5        )            using a sample point ξi obtained from each stratum Aj. Stratifying the integration domain [0,1)s can also be helpful in ensuring that sample points are reasonably well distributed throughout the integration domain [0,1)s, and that they do not clump in the integration domain, which can occur if the locations of the sample points ξi are randomly located in the integration domain.
Several stratification strategies have been proposed. Typically, previously-proposed stratification strategies, particularly stratification strategies that are based on axis-aligned grids, suffer exponential growth in the number of strata with increasing numbers of dimensions comprising the integration domain. Since integrands ƒ that are used in fields such as, for example, computer graphics, often have very high-dimensional integration domains, stratifying domains using such stratification strategies can be computationally quite intensive.